#include<stdio.h>
#include<stdlib.h>

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void print_Arr(int arr[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    putchar('\n');
}
//
void shell_sort(int arr[],int n){
    int i,j,inc,key;
    //初始增量：n/2，每一趟除以2
    for(inc=n/2;inc>0;inc/=2){
        //每一趟采用插入排序
        for(i=inc;i<n;i++){
            key=arr[i];
            for(j=i;j>=inc && key< arr[j-inc];j-=inc){
                arr[j]=arr[j-inc];
            }
            //arr[j-inc]<key或者 key最小了已经
            arr[j]=key;
        }
        print_Arr(arr,n);
    }
}
int main(){
    int arr[6]={30,40,10,14,15,20};
    shell_sort(arr,6);
    return 0;
}